All Questions
Tagged with dynamic-programmingmatrix
13 questions
1vote
1answer
100views
Matrix problem, the path that is the flattest
So in this problem I am given an NxN matrix, in which each value of the matrix represents an altitude. I need to find the best path from the top-left corner to the bottom-right one, my moves being ...
3votes
0answers
1kviews
Python program to solve matrix-chain multiplication
An assignment at school required me to write a Python program for this task: In the matrix-chain multiplication problem, we are given a sequence of matrices ...
- 2,585
4votes
1answer
1kviews
LeetCode 01: Matrix challenge
Recently, I've solved the "01 Matrix" LeetCode problem and the solution was accepted by the LeetCode OJ: Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. ...
- 17.4k
1vote
0answers
4kviews
Traceback in sequence alignment with affine gap penalty (Needleman-Wunsch)
I am working on an implementation of the Needleman-Wunsch sequence alignment algorithm in python, and I've already implemented the one that uses a linear gap penalty equation for scoring, but now I'm ...
- 21
0votes
2answers
423views
google foo.bar max path algorithm puzzle optimization [closed]
I got a programming puzzle described as follows: Save Beta Rabbit Oh no! The mad Professor Boolean has trapped Beta Rabbit in an NxN grid of rooms. In the center of each room (except for the ...
4votes
2answers
3kviews
Optimal matrix chain multiplication in Java
Preliminaries Given two matrices $$ A = \begin{pmatrix} a_{11} & a_{12} & \dots & a_{1q} \\ a_{21} & a_{22} & \dots & a_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ ...
- 30.2k
1vote
2answers
1kviews
LeetCode Minimum Path Sum algorithm
I am attempting to solve the Minimum Path Sum algorithm problem and I have a working solution, however there was an unwritten requirement that the algorithm not exceed an unspecified amount of time ...
- 188
4votes
1answer
946views
Optimizing a dynamic programming solution for "Oil Well"
I'm trying to solve the Oil Well problem on Hackerrank using dynamic programming and it works. However, it times out for some of the test cases. I wanted to know how this program can be improved so ...
- 95
2votes
1answer
230views
Memoization for calculating minimal traversal distance within a positive matrix
The code below is for calculating the minimal traversing distance from the top left point of the matrix to the bottom right point of the matrix. GitHub Here is the core functionality. Please note ...
- 143
4votes
3answers
3kviews
Project Euler 81 (minimum path sum through a matrix)
Problem Statement: In the 5 by 5 matrix below, 131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331 ...
- 5,190
4votes
2answers
342views
Returning all the LIS of given array of int
I have this assignment where I'm supposed to code an algorithm for finding the quantity of Longest Increasing Subsequences from an array of (different) integers and print them all. I developed one ...
- 41
1vote
1answer
1kviews
MaxSum sub matrix within a matrix
Code review for best practices, optimizations, code cleanup etc. Also requesting verification of the complexity: O(row*row*col). ...
- 8,451
2votes
1answer
2kviews
Project Euler #82 - path sum: three ways
Project Euler problem 82 asks: Here's my solution: ...
